using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace Extended.NetRouting
{
    /// <summary>
    /// Provides path resolution extension methods.
    /// </summary>
    public static class Network
    {
        /// <summary>
        /// Gets the shortest path that connects the two nodes. Returns null if none found.
        /// </summary>
        /// <param name="routeProvider">A provider that provides routes between nodes</param>
        /// <param name="start">The starting node.</param>
        /// <param name="target">The target node.</param>
        public static Path GetShortestPath(this IRouteProvider routeProvider, object start, object target)
        {
            if (routeProvider == null) throw new ArgumentNullException("routeProvider");
            if (start == null) throw new ArgumentNullException("start");
            if (target == null) throw new ArgumentNullException("target");

            if (start.Equals(target)) throw new ArgumentException("Start and target match");

            // get all available paths
            var visitor = new RouteVisitor();
            var paths = visitor.GetPaths(routeProvider, start, target, null, false);
            
            // find shortest
            return paths.SelectByMin(p => p.Length);
        }

        /// <summary>
        /// Gets all the paths that connect the two nodes. Returns empty collection if none found.
        /// </summary>
        /// <param name="routeProvider">A provider that provides routes between nodes</param>
        /// <param name="start">The starting node.</param>
        /// <param name="target">The target node.</param>
        public static IEnumerable<Path> GetPaths(this IRouteProvider routeProvider, object start, object target)
        {
            if (routeProvider == null) throw new ArgumentNullException("routeProvider");
            if (start == null) throw new ArgumentNullException("start");
            if (target == null) throw new ArgumentNullException("target");

            if (start.Equals(target)) throw new ArgumentException("Start and target match");

            var visitor = new RouteVisitor();
            return visitor.GetPaths(routeProvider, start, target, null, true);
        }

        // GetPaths method inside this class could be static and the class could have been avoided. It is here because
        // we want to keep a reference to the current best path during a search and iterator methods (methods that return
        // IEnumerable) cannot have ref or out parameters.
        internal class RouteVisitor
        {
            // Holds a reference to the current best path during a search
            private Path currentBestPath;

#if DEBUG
            public RouteVisitor()
            {
                ExhaustedPaths = 0;
            }

            // Number of paths exhausted (kept for unit test purposes, in order to assert that the algorithm skipped
            // a number of paths whenever it detected that their length is longer than the best path that have been found
            // so far)
            public static int ExhaustedPaths { get; private set; }
#endif

            internal IEnumerable<Path> GetPaths(IRouteProvider routeProvider, object start, object target, Path currentPath, bool findAll)
            {
                // loop all routes that start from the specified starting node
                foreach (var route in routeProvider.GetRoutesFromNode(start))
                {
                    // if path so far already contains the next node of current route then
                    // a loop has been completed. Continue to the next available route
                    if (currentPath != null && currentPath.Contains(route.Target)) continue;

                    // create a new path that continues from the current path
                    // and add the next node of current route
                    var newPath = new Path(currentPath) { route };

                    Debug.WriteLine("Current path: " + newPath.ToNodeString("."));

                    // if current path (with the addition of the current route of the foreach loop)
                    // if already longer than the best path already found then there is not need to continue
                    // with the search
                    var currentPathIsNotBetter = this.currentBestPath != null && this.currentBestPath.Length <= newPath.Length;
                    if (!findAll && currentPathIsNotBetter)
                    {
                        Debug.WriteLine("Skipping path because it is already too long");
                        continue;
                    }

                    // if the next node is our target then save the path and continue to the next route
                    if (route.Target == target)
                    {
                        // keep a reference to the best path until now, in order to
                        // avoid following paths that exceed it's length
                        if (!currentPathIsNotBetter)
                        {
                            this.currentBestPath = newPath;
                        }

                        Debug.WriteLine("Picking current path");
                        yield return newPath;
                        continue;
                    }

                    // follow the routes that start from the end of the current route
                    // TODO : SEE IF THERE IS BETTER WAY TO HANDLE RECURSIVE (NESTED) YIELD RETURN STATEMENTS
                    Debug.WriteLine("Going deeper on current path");
                    Debug.Indent();
                    foreach (var path in this.GetPaths(routeProvider, route.Target, target, newPath, findAll))
                    {
                        yield return path;
                    }

#if DEBUG
                    ExhaustedPaths++;
#endif
                    Debug.WriteLine("Current path exchausted. No match found.");
                    Debug.Unindent();
                }
            }
        }
    }
}